package dataStructure.linkedList.binaryTree;

import letcode.util.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @Description: 二叉树的后序遍历
 * @Date: 2020/4/22
 * @Author: 许群星
 */
public class PostorderTraversal {
    //顺序：左右中

    //递归
    ArrayList<Integer> list = new ArrayList<>();

    public List<Integer> postorder(TreeNode root) {
        //为空则返回
        if (root == null)
            return list;

        if (root.left != null)
            postorder(root.left);
        if (root.right != null)
            postorder(root.right);
        list.add(root.val);

        return list;
    }

    //迭代
    public List<Integer> postorder_diedai(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        LinkedList<Integer> res = new LinkedList<>();
        TreeNode curr = root;
        TreeNode last = null;

        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }

            curr = stack.peek();

            if (curr.right == null || curr.right == last) {
                res.add(curr.val);
                stack.pop();
                last = curr;
                curr = null;
            } else
                curr = curr.right;
        }
        return res;
    }
}
